<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 3.4</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 3.4" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 3.4" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-3.xhtml#Chapter-3" rel="prev" title="Chapter 3" />
<link href="3_002e5.xhtml#g_t3_002e5" rel="next" title="3.5" />
<link href="3_002e3.xhtml#g_t3_002e3_002e5" rel="prev" title="3.3.5" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t3_002e4"></a>
<nav class="header">
<p>
Next: <a href="3_002e5.xhtml#g_t3_002e5" accesskey="n" rel="next">3.5</a>, Prev: <a href="3_002e3.xhtml#g_t3_002e3" accesskey="p" rel="prev">3.3</a>, Up: <a href="Chapter-3.xhtml#Chapter-3" accesskey="u" rel="prev">Chapter 3</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Concurrency_003a-Time-Is-of-the-Essence"></a>
<h3 class="section"><span class="secnum">3.4</span><span class="sectitle">Concurrency: Time Is of the Essence</span></h3>

<p>We’ve seen the power of computational objects with local state as tools for
modeling.  Yet, as <a href="3_002e1.xhtml#g_t3_002e1_002e3">3.1.3</a> warned, this power extracts a price: the
loss of referential transparency, giving rise to a thicket of questions about
sameness and change, and the need to abandon the substitution model of
evaluation in favor of the more intricate environment model.
</p>
<p>The central issue lurking beneath the complexity of state, sameness, and change
is that by introducing assignment we are forced to admit <a id="index-time"></a>
<em>time</em> into
our computational models.  Before we introduced assignment, all our programs
were timeless, in the sense that any expression that has a value always has the
same value.  In contrast, recall the example of modeling withdrawals from a
bank account and returning the resulting balance, introduced at the beginning
of <a href="3_002e1.xhtml#g_t3_002e1_002e1">3.1.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">withdraw </span><span class="lit">25</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">75</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">withdraw </span><span class="lit">25</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">50</span></i>
</pre></div>

<p>Here successive evaluations of the same expression yield different values.
This behavior arises from the fact that the execution of assignment statements
(in this case, assignments to the variable <code>balance</code>) delineates
<a id="index-moments-in-time"></a>
<em>moments in time</em> when values change.  The result of evaluating an
expression depends not only on the expression itself, but also on whether the
evaluation occurs before or after these moments.  Building models in terms of
computational objects with local state forces us to confront time as an
essential concept in programming.
</p>
<p>We can go further in structuring computational models to match our perception
of the physical world.  Objects in the world do not change one at a time in
sequence.  Rather we perceive them as acting <a id="index-concurrently"></a>
<em>concurrently</em>—all at
once.  So it is often natural to model systems as collections of computational
processes that execute concurrently.  Just as we can make our programs modular
by organizing models in terms of objects with separate local state, it is often
appropriate to divide computational models into parts that evolve separately
and concurrently.  Even if the programs are to be executed on a sequential
computer, the practice of writing programs as if they were to be executed
concurrently forces the programmer to avoid inessential timing constraints and
thus makes programs more modular.
</p>
<p>In addition to making programs more modular, concurrent computation can provide
a speed advantage over sequential computation.  Sequential computers execute
only one operation at a time, so the amount of time it takes to perform a task
is proportional to the total number of operations performed.<a class="footnote_link" id="DOCF162" href="#FOOT162"><sup>162</sup></a>  However, if it is possible to decompose a problem
into pieces that are relatively independent and need to communicate only
rarely, it may be possible to allocate pieces to separate computing processors,
producing a speed advantage proportional to the number of processors available.
</p>
<p>Unfortunately, the complexities introduced by assignment become even more
problematic in the presence of concurrency.  The fact of concurrent execution,
either because the world operates in parallel or because our computers do,
entails additional complexity in our understanding of time.
</p>

<a id="g_t3_002e4_002e1"></a>
<a id="The-Nature-of-Time-in-Concurrent-Systems"></a>
<h4 class="subsection"><span class="secnum">3.4.1</span><span class="sectitle">The Nature of Time in Concurrent Systems</span></h4>

<p>On the surface, time seems straightforward.  It is an ordering imposed on
events.<a class="footnote_link" id="DOCF163" href="#FOOT163"><sup>163</sup></a>  For any events <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>B</mi>
</math>, either <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math> occurs before <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>B</mi>
</math>,
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>B</mi>
</math> are simultaneous, or <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math> occurs after <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>B</mi>
</math>.  For instance,
returning to the bank account example, suppose that Peter withdraws $10 and
Paul withdraws $25 from a joint account that initially contains $100, leaving
$65 in the account.  Depending on the order of the two withdrawals, the
sequence of balances in the account is either $100 <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">→<!-- → --></mo>
</math> $90 <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">→<!-- → --></mo>
</math> $65 or $100 <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">→<!-- → --></mo>
</math> $75
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">→<!-- → --></mo>
</math> $65.  In a computer implementation of the banking system, this changing
sequence of balances could be modeled by successive assignments to a variable
<code>balance</code>.
</p>
<p>In complex situations, however, such a view can be problematic.  Suppose that
Peter and Paul, and other people besides, are accessing the same bank account
through a network of banking machines distributed all over the world.  The
actual sequence of balances in the account will depend critically on the
detailed timing of the accesses and the details of the communication among the
machines.
</p>
<p>This indeterminacy in the order of events can pose serious problems in the
design of concurrent systems.  For instance, suppose that the withdrawals made
by Peter and Paul are implemented as two separate processes sharing a common
variable <code>balance</code>, each process specified by the procedure given in
<a href="3_002e1.xhtml#g_t3_002e1_002e1">3.1.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">withdraw amount</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> 
        </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance 
              </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
        balance</span><span class="clo">)</span><span class="pln">
      </span><span class="str">"Insufficient funds"</span><span class="clo">))</span></pre></div>

<p>If the two processes operate independently, then Peter might test the
balance and attempt to withdraw a legitimate amount.  However, Paul
might withdraw some funds in between the time that Peter checks the
balance and the time Peter completes the withdrawal, thus invalidating
Peter’s test.
</p>
<p>Things can be worse still.  Consider the expression
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span></pre></div>

<p>executed as part of each withdrawal process.  This consists of three steps: (1)
accessing the value of the <code>balance</code> variable; (2) computing the new
balance; (3) setting <code>balance</code> to this new value.  If Peter and Paul’s
withdrawals execute this statement concurrently, then the two withdrawals might
interleave the order in which they access <code>balance</code> and set it to the new
value.
</p>
<p>The timing diagram in <a href="#Figure-3_002e29">Figure 3.29</a> depicts an order of events where
<code>balance</code> starts at 100, Peter withdraws 10, Paul withdraws 25, and yet
the final value of <code>balance</code> is 75.  As shown in the diagram, the reason
for this anomaly is that Paul’s assignment of 75 to <code>balance</code> is made
under the assumption that the value of <code>balance</code> to be decremented is 100.
That assumption, however, became invalid when Peter changed <code>balance</code> to
90.  This is a catastrophic failure for the banking system, because the total
amount of money in the system is not conserved.  Before the transactions, the
total amount of money was $100.  Afterwards, Peter has $10, Paul has $25, and
the bank has $75.<a class="footnote_link" id="DOCF164" href="#FOOT164"><sup>164</sup></a>
</p>
<figure class="float">
<a id="Figure-3_002e29"></a>
<object style="width: 60.18ex; height: 57.93ex;" data="fig/chap3/Fig3.29b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.29:</strong> Timing diagram showing how interleaving the order of events in two banking withdrawals can lead to an incorrect final balance.</p>
</figcaption>
</figure>

<p>The general phenomenon illustrated here is that several processes may share a
common state variable.  What makes this complicated is that more than one
process may be trying to manipulate the shared state at the same time.  For the
bank account example, during each transaction, each customer should be able to
act as if the other customers did not exist.  When a customer changes the
balance in a way that depends on the balance, he must be able to assume that,
just before the moment of change, the balance is still what he thought it was.
</p>
<a id="Correct-behavior-of-concurrent-programs"></a>
<h5 class="subsubheading">Correct behavior of concurrent programs</h5>

<p>The above example typifies the subtle bugs that can creep into concurrent
programs.  The root of this complexity lies in the assignments to variables
that are shared among the different processes.  We already know that we must be
careful in writing programs that use <code>set!</code>, because the results of a
computation depend on the order in which the assignments occur.<a class="footnote_link" id="DOCF165" href="#FOOT165"><sup>165</sup></a>  With concurrent processes we must be especially careful
about assignments, because we may not be able to control the order of the
assignments made by the different processes.  If several such changes might be
made concurrently (as with two depositors accessing a joint account) we need
some way to ensure that our system behaves correctly.  For example, in the case
of withdrawals from a joint bank account, we must ensure that money is
conserved.  To make concurrent programs behave correctly, we may have to place
some restrictions on concurrent execution.
</p>
<p>One possible restriction on concurrency would stipulate that no two operations
that change any shared state variables can occur at the same time.  This is an
extremely stringent requirement.  For distributed banking, it would require the
system designer to ensure that only one transaction could proceed at a time.
This would be both inefficient and overly conservative.  <a href="#Figure-3_002e30">Figure 3.30</a>
shows Peter and Paul sharing a bank account, where Paul has a private account
as well.  The diagram illustrates two withdrawals from the shared account (one
by Peter and one by Paul) and a deposit to Paul’s private account.<a class="footnote_link" id="DOCF166" href="#FOOT166"><sup>166</sup></a>  The two withdrawals from the
shared account must not be concurrent (since both access and update the same
account), and Paul’s deposit and withdrawal must not be concurrent (since both
access and update the amount in Paul’s wallet).  But there should be no problem
permitting Paul’s deposit to his private account to proceed concurrently with
Peter’s withdrawal from the shared account.
</p>
<figure class="float">
<a id="Figure-3_002e30"></a>
<object style="width: 67.52ex; height: 52.84ex;" data="fig/chap3/Fig3.30c.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.30:</strong> Concurrent deposits and withdrawals from a joint account in Bank1 and a private account in Bank2.</p>
</figcaption>
</figure>

<p>A less stringent restriction on concurrency would ensure that a concurrent
system produces the same result as if the processes had run sequentially in
some order.  There are two important aspects to this requirement.  First, it
does not require the processes to actually run sequentially, but only to
produce results that are the same <em>as if</em> they had run sequentially.  For
the example in <a href="#Figure-3_002e30">Figure 3.30</a>, the designer of the bank account system can
safely allow Paul’s deposit and Peter’s withdrawal to happen concurrently,
because the net result will be the same as if the two operations had happened
sequentially.  Second, there may be more than one possible “correct” result
produced by a concurrent program, because we require only that the result be
the same as for <em>some</em> sequential order.  For example, suppose that Peter
and Paul’s joint account starts out with $100, and Peter deposits $40 while
Paul concurrently withdraws half the money in the account.  Then sequential
execution could result in the account balance being either $70 or $90 (see
<a href="#Exercise-3_002e38">Exercise 3.38</a>).<a class="footnote_link" id="DOCF167" href="#FOOT167"><sup>167</sup></a>
</p>
<p>There are still weaker requirements for correct execution of concurrent
programs.  A program for simulating diffusion (say, the flow of heat in an
object) might consist of a large number of processes, each one representing a
small volume of space, that update their values concurrently.  Each process
repeatedly changes its value to the average of its own value and its neighbors’
values.  This algorithm converges to the right answer independent of the order
in which the operations are done; there is no need for any restrictions on
concurrent use of the shared values.
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e38"></a>Exercise 3.38:</strong> Suppose that Peter, Paul, and
Mary share a joint bank account that initially contains $100.  Concurrently,
Peter deposits $10, Paul withdraws $20, and Mary withdraws half the money in
the account, by executing the following commands:
</p>
<div class="example">
<pre class="example">Peter: (set! balance (+ balance 10))
Paul:  (set! balance (- balance 20))
Mary:  (set! balance (- balance 
                        (/ balance 2)))
</pre></div>

<ol>
<li> List all the different possible values for <code>balance</code> after these three
transactions have been completed, assuming that the banking system forces the
three processes to run sequentially in some order.

</li><li> What are some other values that could be produced if the system allows the
processes to be interleaved?  Draw timing diagrams like the one in <a href="#Figure-3_002e29">Figure 3.29</a> 
to explain how these values can occur.

</li></ol>
</blockquote>

<a id="g_t3_002e4_002e2"></a>
<a id="Mechanisms-for-Controlling-Concurrency"></a>
<h4 class="subsection"><span class="secnum">3.4.2</span><span class="sectitle">Mechanisms for Controlling Concurrency</span></h4>

<p>We’ve seen that the difficulty in dealing with concurrent processes is rooted
in the need to consider the interleaving of the order of events in the
different processes.  For example, suppose we have two processes, one with
three ordered events <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>a</mi>
    <mo>,</mo>
    <mi>b</mi>
    <mo>,</mo>
    <mi>c</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> and one with three ordered events
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo>,</mo>
    <mi>y</mi>
    <mo>,</mo>
    <mi>z</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  If the two processes run concurrently, with no
constraints on how their execution is interleaved, then there are 20 different
possible orderings for the events that are consistent with the individual
orderings for the two processes:
</p>
<div class="example">
<pre class="example">(a,b,c,x,y,z)  (a,x,b,y,c,z)  (x,a,b,c,y,z)  
(x,a,y,z,b,c)  (a,b,x,c,y,z)  (a,x,b,y,z,c)  
(x,a,b,y,c,z)  (x,y,a,b,c,z)  (a,b,x,y,c,z)  
(a,x,y,b,c,z)  (x,a,b,y,z,c)  (x,y,a,b,z,c)
(a,b,x,y,z,c)  (a,x,y,b,z,c)  (x,a,y,b,c,z)  
(x,y,a,z,b,c)  (a,x,b,c,y,z)  (a,x,y,z,b,c)  
(x,a,y,b,z,c)  (x,y,z,a,b,c)
</pre></div>

<p>As programmers designing this system, we would have to consider the effects of
each of these 20 orderings and check that each behavior is acceptable.  Such an
approach rapidly becomes unwieldy as the numbers of processes and events
increase.
</p>
<p>A more practical approach to the design of concurrent systems is to devise
general mechanisms that allow us to constrain the interleaving of concurrent
processes so that we can be sure that the program behavior is correct.  Many
mechanisms have been developed for this purpose.  In this section, we describe
one of them, the <a id="index-serializer"></a>
<em>serializer</em>.
</p>
<a id="Serializing-access-to-shared-state"></a>
<h5 class="subsubheading">Serializing access to shared state</h5>

<p>Serialization implements the following idea: Processes will execute
concurrently, but there will be certain collections of procedures that cannot
be executed concurrently.  More precisely, serialization creates distinguished
sets of procedures such that only one execution of a procedure in each
serialized set is permitted to happen at a time.  If some procedure in the set
is being executed, then a process that attempts to execute any procedure in the
set will be forced to wait until the first execution has finished.
</p>
<p>We can use serialization to control access to shared variables.  For example,
if we want to update a shared variable based on the previous value of that
variable, we put the access to the previous value of the variable and the
assignment of the new value to the variable in the same procedure.  We then
ensure that no other procedure that assigns to the variable can run
concurrently with this procedure by serializing all of these procedures with
the same serializer.  This guarantees that the value of the variable cannot be
changed between an access and the corresponding assignment.
</p>
<a id="Serializers-in-Scheme"></a>
<h5 class="subsubheading">Serializers in Scheme</h5>

<p>To make the above mechanism more concrete, suppose that we have extended Scheme
to include a procedure called <code>parallel-execute</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">parallel-execute ⟨</span><var><span class="pln">p</span><span class="pun">₁</span></var><span class="pln">⟩ 
                  ⟨</span><var><span class="pln">p</span><span class="pun">₂</span></var><span class="pln">⟩ 
                  </span><span class="roman"><span class="pun">…</span></span><span class="pln"> 
                  ⟨</span><var><span class="pln">p</span><span class="pun">ₖ</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>Each <code>⟨</code><var>p</var><code>⟩</code> must be a procedure of no arguments.  <code>Parallel-execute</code>
creates a separate process for each <code>⟨</code><var>p</var><code>⟩</code>, which applies 
<code>⟨</code><var>p</var><code>⟩</code> (to no arguments).  These processes all run
concurrently.<a class="footnote_link" id="DOCF168" href="#FOOT168"><sup>168</sup></a>
</p>
<p>As an example of how this is used, consider
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">parallel-execute </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x</span><span class="clo">)))</span><span class="pln">
                  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">1</span><span class="clo">))))</span></pre></div>

<p>This creates two concurrent processes—<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math>, which sets <code>x</code> to
<code>x</code> times <code>x</code>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>2</mn>
  </msub>
</math>, which increments <code>x</code>.  After
execution is complete, <code>x</code> will be left with one of five possible values,
depending on the interleaving of the events of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>2</mn>
  </msub>
</math>:
</p>
<div class="example">
<pre class="example">101: <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math> sets <code>x</code> to 100 and then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>2</mn>
  </msub>
</math> increments
     <code>x</code> to 101.
121: <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>2</mn>
  </msub>
</math> increments <code>x</code> to 11 and then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math> sets
     <code>x</code> to <code>x</code> times <code>x</code>.
110: <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>2</mn>
  </msub>
</math> changes <code>x</code> from 10 to 11 between the 
     two times that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math> accesses the value of 
     <code>x</code> during the evaluation of <code>(* x x)</code>.
 11: <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>2</mn>
  </msub>
</math> accesses <code>x</code>, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math> sets <code>x</code> to 100, 
     then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>2</mn>
  </msub>
</math> sets <code>x</code>.
100: <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math> accesses <code>x</code> (twice), then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>2</mn>
  </msub>
</math> sets
     <code>x</code> to 11, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math> sets <code>x</code>.
</pre></div>

<p>We can constrain the concurrency by using serialized procedures, which are
created by <a id="index-serializers"></a>
<em>serializers</em>. Serializers are constructed by
<code>make-serializer</code>, whose implementation is given below.  A serializer
takes a procedure as argument and returns a serialized procedure that behaves
like the original procedure.  All calls to a given serializer return serialized
procedures in the same set.
</p>
<p>Thus, in contrast to the example above, executing
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> s </span><span class="opn">(</span><span class="pln">make-serializer</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">parallel-execute 
 </span><span class="opn">(</span><span class="pln">s </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x</span><span class="clo">))))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">s </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>

<p>can produce only two possible values for <code>x</code>, 101 or 121.  The other
possibilities are eliminated, because the execution of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>2</mn>
  </msub>
</math>
cannot be interleaved.
</p>
<p>Here is a version of the <code>make-account</code> procedure from 
<a href="3_002e1.xhtml#g_t3_002e1_002e1">3.1.1</a>, where the deposits and withdrawals have been serialized:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-account balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">withdraw amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance 
                     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
               balance</span><span class="clo">)</span><span class="pln">
        </span><span class="str">"Insufficient funds"</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">deposit amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
    balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">protected </span><span class="opn">(</span><span class="pln">make-serializer</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pln">protected withdraw</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pln">protected deposit</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'balance</span><span class="clo">)</span><span class="pln"> 
             balance</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: 
                          MAKE-ACCOUNT"</span><span class="pln">
                         m</span><span class="clo">))))</span><span class="pln">
    dispatch</span><span class="clo">))</span></pre></div>

<p>With this implementation, two processes cannot be withdrawing from or
depositing into a single account concurrently.  This eliminates the source of
the error illustrated in <a href="#Figure-3_002e29">Figure 3.29</a>, where Peter changes the account
balance between the times when Paul accesses the balance to compute the new
value and when Paul actually performs the assignment.  On the other hand, each
account has its own serializer, so that deposits and withdrawals for different
accounts can proceed concurrently.
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e39"></a>Exercise 3.39:</strong> Which of the five possibilities
in the parallel execution shown above remain if we instead serialize execution
as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> s </span><span class="opn">(</span><span class="pln">make-serializer</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">parallel-execute 
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> 
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">((</span><span class="pln">s </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x</span><span class="clo">))))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">s </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e40"></a>Exercise 3.40:</strong> Give all possible values of
<code>x</code> that can result from executing
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">parallel-execute 
 </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x</span><span class="clo">)))</span><span class="pln">
 </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x x</span><span class="clo">))))</span></pre></div>

<p>Which of these possibilities remain if we instead use serialized procedures:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> s </span><span class="opn">(</span><span class="pln">make-serializer</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">parallel-execute 
 </span><span class="opn">(</span><span class="pln">s </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x</span><span class="clo">))))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">s </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x x</span><span class="clo">)))))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e41"></a>Exercise 3.41:</strong> Ben Bitdiddle worries that it
would be better to implement the bank account as follows (where the commented
line has been changed):
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-account balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">withdraw amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> 
          </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance 
                </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
          balance</span><span class="clo">)</span><span class="pln">
        </span><span class="str">"Insufficient funds"</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">deposit amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
    balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">protected </span><span class="opn">(</span><span class="pln">make-serializer</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pln">protected withdraw</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pln">protected deposit</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'balance</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">((</span><span class="pln">protected 
                </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> 
                  balance</span><span class="clo">))))</span><span class="pln"> </span><span class="roman"><span class="com">; serialized</span></span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
             </span><span class="opn">(</span><span class="err">error</span><span class="pln"> 
              </span><span class="str">"Unknown request: 
               MAKE-ACCOUNT"</span><span class="pln">
              m</span><span class="clo">))))</span><span class="pln">
    dispatch</span><span class="clo">))</span></pre></div>

<p>because allowing unserialized access to the bank balance can result in
anomalous behavior.  Do you agree?  Is there any scenario that demonstrates
Ben’s concern?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e42"></a>Exercise 3.42:</strong> Ben Bitdiddle suggests that it’s
a waste of time to create a new serialized procedure in response to every
<code>withdraw</code> and <code>deposit</code> message.  He says that <code>make-account</code>
could be changed so that the calls to <code>protected</code> are done outside the
<code>dispatch</code> procedure.  That is, an account would return the same
serialized procedure (which was created at the same time as the account) each
time it is asked for a withdrawal procedure.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-account balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">withdraw amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance 
                     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
               balance</span><span class="clo">)</span><span class="pln">
        </span><span class="str">"Insufficient funds"</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">deposit amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
    balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">protected </span><span class="opn">(</span><span class="pln">make-serializer</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">protected-withdraw 
           </span><span class="opn">(</span><span class="pln">protected withdraw</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">protected-deposit 
           </span><span class="opn">(</span><span class="pln">protected deposit</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> 
               protected-withdraw</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> 
               protected-deposit</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'balance</span><span class="clo">)</span><span class="pln"> 
               balance</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
               </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: 
                       MAKE-ACCOUNT"</span><span class="pln">
                      m</span><span class="clo">))))</span><span class="pln">
      dispatch</span><span class="clo">)))</span></pre></div>

<p>Is this a safe change to make?  In particular, is there any difference in what
concurrency is allowed by these two versions of <code>make-account</code>?
</p></blockquote>

<a id="Complexity-of-using-multiple-shared-resources"></a>
<h5 class="subsubheading">Complexity of using multiple shared resources</h5>

<p>Serializers provide a powerful abstraction that helps isolate the complexities
of concurrent programs so that they can be dealt with carefully and (hopefully)
correctly.  However, while using serializers is relatively straightforward when
there is only a single shared resource (such as a single bank account),
concurrent programming can be treacherously difficult when there are multiple
shared resources.
</p>
<p>To illustrate one of the difficulties that can arise, suppose we wish to swap
the balances in two bank accounts.  We access each account to find the balance,
compute the difference between the balances, withdraw this difference from one
account, and deposit it in the other account.  We could implement this as
follows:<a class="footnote_link" id="DOCF169" href="#FOOT169"><sup>169</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">exchange account1 account2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">difference </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">account1 </span><span class="lit">'balance</span><span class="clo">)</span><span class="pln">
                       </span><span class="opn">(</span><span class="pln">account2 </span><span class="lit">'balance</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">((</span><span class="pln">account1 </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> difference</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">((</span><span class="pln">account2 </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> difference</span><span class="clo">)))</span></pre></div>

<p>This procedure works well when only a single process is trying to do the
exchange.  Suppose, however, that Peter and Paul both have access to accounts
<math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>1</mn>
</mrow>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>2</mn>
</mrow>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>3</mn>
</mrow>
</math>, and that Peter exchanges <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>1</mn>
</mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>2</mn>
</mrow>
</math> while
Paul concurrently exchanges <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>1</mn>
</mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>3</mn>
</mrow>
</math>.  Even with account deposits and
withdrawals serialized for individual accounts (as in the <code>make-account</code>
procedure shown above in this section), <code>exchange</code> can still produce
incorrect results.  For example, Peter might compute the difference in the
balances for <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>1</mn>
</mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>2</mn>
</mrow>
</math>, but then Paul might change the balance in
<math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>1</mn>
</mrow>
</math> before Peter is able to complete the exchange.<a class="footnote_link" id="DOCF170" href="#FOOT170"><sup>170</sup></a>  For correct behavior, we must arrange for the
<code>exchange</code> procedure to lock out any other concurrent accesses to the
accounts during the entire time of the exchange.
</p>
<p>One way we can accomplish this is by using both accounts’ serializers to
serialize the entire <code>exchange</code> procedure.  To do this, we will arrange
for access to an account’s serializer.  Note that we are deliberately breaking
the modularity of the bank-account object by exposing the serializer.  The
following version of <code>make-account</code> is identical to the original version
given in <a href="3_002e1.xhtml#g_t3_002e1_002e1">3.1.1</a>, except that a serializer is provided to protect
the balance variable, and the serializer is exported via message passing:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-account-and-serializer balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">withdraw amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> 
          </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
          balance</span><span class="clo">)</span><span class="pln">
        </span><span class="str">"Insufficient funds"</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">deposit amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
    balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">balance-serializer 
         </span><span class="opn">(</span><span class="pln">make-serializer</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> withdraw</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> deposit</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'balance</span><span class="clo">)</span><span class="pln"> balance</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'serializer</span><span class="clo">)</span><span class="pln"> 
             balance-serializer</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: 
                          MAKE-ACCOUNT"</span><span class="pln">
                         m</span><span class="clo">))))</span><span class="pln">
    dispatch</span><span class="clo">))</span></pre></div>

<p>We can use this to do serialized deposits and withdrawals.  However, unlike our
earlier serialized account, it is now the responsibility of each user of
bank-account objects to explicitly manage the serialization, for example as
follows:<a class="footnote_link" id="DOCF171" href="#FOOT171"><sup>171</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">deposit account amount</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">s </span><span class="opn">(</span><span class="pln">account </span><span class="lit">'serializer</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">d </span><span class="opn">(</span><span class="pln">account </span><span class="lit">'deposit</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">((</span><span class="pln">s d</span><span class="clo">)</span><span class="pln"> amount</span><span class="clo">)))</span></pre></div>

<p>Exporting the serializer in this way gives us enough flexibility to implement a
serialized exchange program.  We simply serialize the original <code>exchange</code>
procedure with the serializers for both accounts:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">serialized-exchange account1 account2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">serializer1 </span><span class="opn">(</span><span class="pln">account1 </span><span class="lit">'serializer</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">serializer2 </span><span class="opn">(</span><span class="pln">account2 </span><span class="lit">'serializer</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">((</span><span class="pln">serializer1 </span><span class="opn">(</span><span class="pln">serializer2 exchange</span><span class="clo">))</span><span class="pln">
     account1
     account2</span><span class="clo">)))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-3_002e43"></a>Exercise 3.43:</strong> Suppose that the balances in
three accounts start out as $10, $20, and $30, and that multiple processes run,
exchanging the balances in the accounts.  Argue that if the processes are run
sequentially, after any number of concurrent exchanges, the account balances
should be $10, $20, and $30 in some order.  Draw a timing diagram like the one
in <a href="#Figure-3_002e29">Figure 3.29</a> to show how this condition can be violated if the
exchanges are implemented using the first version of the account-exchange
program in this section.  On the other hand, argue that even with this
<code>exchange</code> program, the sum of the balances in the accounts will be
preserved.  Draw a timing diagram to show how even this condition would be
violated if we did not serialize the transactions on individual accounts.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e44"></a>Exercise 3.44:</strong> Consider the problem of
transferring an amount from one account to another.  Ben Bitdiddle claims that
this can be accomplished with the following procedure, even if there are
multiple people concurrently transferring money among multiple accounts, using
any account mechanism that serializes deposit and withdrawal transactions, for
example, the version of <code>make-account</code> in the text above.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">transfer from-account to-account amount</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">from-account </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> amount</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">to-account </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> amount</span><span class="clo">))</span></pre></div>

<p>Louis Reasoner claims that there is a problem here, and that we need to use a
more sophisticated method, such as the one required for dealing with the
exchange problem.  Is Louis right?  If not, what is the essential difference
between the transfer problem and the exchange problem?  (You should assume that
the balance in <code>from-account</code> is at least <code>amount</code>.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e45"></a>Exercise 3.45:</strong> Louis Reasoner thinks our
bank-account system is unnecessarily complex and error-prone now that deposits
and withdrawals aren’t automatically serialized.  He suggests that
<code>make-account-and-serializer</code> should have exported the serializer (for use
by such procedures as <code>serialized-exchange</code>) in addition to (rather than
instead of) using it to serialize accounts and deposits as <code>make-account</code>
did.  He proposes to redefine accounts as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">make-account-and-serializer balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">withdraw amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance 
                     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
               balance</span><span class="clo">)</span><span class="pln">
        </span><span class="str">"Insufficient funds"</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">deposit amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
    balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">balance-serializer 
         </span><span class="opn">(</span><span class="pln">make-serializer</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pln">balance-serializer withdraw</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pln">balance-serializer deposit</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'balance</span><span class="clo">)</span><span class="pln"> 
             balance</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'serializer</span><span class="clo">)</span><span class="pln"> 
             balance-serializer</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: 
                          MAKE-ACCOUNT"</span><span class="pln">
                         m</span><span class="clo">))))</span><span class="pln">
    dispatch</span><span class="clo">))</span></pre></div>

<p>Then deposits are handled as with the original <code>make-account</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">deposit account amount</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">account </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> amount</span><span class="clo">))</span></pre></div>

<p>Explain what is wrong with Louis’s reasoning.  In particular, consider what
happens when <code>serialized-exchange</code> is called.
</p></blockquote>

<a id="Implementing-serializers"></a>
<h5 class="subsubheading">Implementing serializers</h5>

<p>We implement serializers in terms of a more primitive synchronization mechanism
called a <a id="index-mutex"></a>
<em>mutex</em>.  A mutex is an object that supports two
operations—the mutex can be <a id="index-acquired"></a>
<em>acquired</em>, and the mutex can be
<a id="index-released"></a>
<em>released</em>.  Once a mutex has been acquired, no other acquire
operations on that mutex may proceed until the mutex is released.<a class="footnote_link" id="DOCF172" href="#FOOT172"><sup>172</sup></a> In our implementation, each
serializer has an associated mutex.  Given a procedure <code>p</code>, the serializer
returns a procedure that acquires the mutex, runs <code>p</code>, and then releases
the mutex.  This ensures that only one of the procedures produced by the
serializer can be running at once, which is precisely the serialization
property that we need to guarantee.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-serializer</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">mutex </span><span class="opn">(</span><span class="pln">make-mutex</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">p</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">serialized-p </span><span class="pun">.</span><span class="pln"> args</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">mutex </span><span class="lit">'acquire</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">val </span><span class="opn">(</span><span class="pln">apply p args</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">mutex </span><span class="lit">'release</span><span class="clo">)</span><span class="pln">
          val</span><span class="clo">))</span><span class="pln">
      serialized-p</span><span class="clo">)))</span></pre></div>

<p>The mutex is a mutable object (here we’ll use a one-element list, which we’ll
refer to as a <a id="index-cell"></a>
<em>cell</em>) that can hold the value true or false.  When the
value is false, the mutex is available to be acquired.  When the value is true,
the mutex is unavailable, and any process that attempts to acquire the mutex
must wait.
</p>
<p>Our mutex constructor <code>make-mutex</code> begins by initializing the cell
contents to false.  To acquire the mutex, we test the cell.  If the mutex is
available, we set the cell contents to true and proceed.  Otherwise, we wait in
a loop, attempting to acquire over and over again, until we find that the mutex
is available.<a class="footnote_link" id="DOCF173" href="#FOOT173"><sup>173</sup></a>  To release the
mutex, we set the cell contents to false.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-mutex</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">cell </span><span class="opn">(</span><span class="pln">list false</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">the-mutex m</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'acquire</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">test-and-set! cell</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">the-mutex </span><span class="lit">'acquire</span><span class="clo">)))</span><span class="pln"> </span><span class="roman"><span class="com">; retry</span></span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'release</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">clear! cell</span><span class="clo">))))</span><span class="pln">
    the-mutex</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">clear! cell</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-car! cell false</span><span class="clo">))</span></pre></div>

<p><code>Test-and-set!</code> tests the cell and returns the result of the test.  In
addition, if the test was false, <code>test-and-set!</code> sets the cell contents to
true before returning false.  We can express this behavior as the following
procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">test-and-set! cell</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> cell</span><span class="clo">)</span><span class="pln">
      true
      </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-car! cell true</span><span class="clo">)</span><span class="pln">
             false</span><span class="clo">)))</span></pre></div>

<p>However, this implementation of <code>test-and-set!</code> does not suffice as it
stands.  There is a crucial subtlety here, which is the essential place where
concurrency control enters the system: The <code>test-and-set!</code> operation must
be performed <a id="index-atomically"></a>
<em>atomically</em>.  That is, we must guarantee that, once a
process has tested the cell and found it to be false, the cell contents will
actually be set to true before any other process can test the cell.  If we do
not make this guarantee, then the mutex can fail in a way similar to the
bank-account failure in <a href="#Figure-3_002e29">Figure 3.29</a>.  (See <a href="#Exercise-3_002e46">Exercise 3.46</a>.)
</p>
<p>The actual implementation of <code>test-and-set!</code> depends on the details of how
our system runs concurrent processes.  For example, we might be executing
concurrent processes on a sequential processor using a time-slicing mechanism
that cycles through the processes, permitting each process to run for a short
time before interrupting it and moving on to the next process.  In that case,
<code>test-and-set!</code>  can work by disabling time slicing during the testing and
setting.<a class="footnote_link" id="DOCF174" href="#FOOT174"><sup>174</sup></a>  Alternatively, multiprocessing computers provide
instructions that support atomic operations directly in
hardware.<a class="footnote_link" id="DOCF175" href="#FOOT175"><sup>175</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e46"></a>Exercise 3.46:</strong> Suppose that we implement
<code>test-and-set!</code>  using an ordinary procedure as shown in the text, without
attempting to make the operation atomic.  Draw a timing diagram like the one in
<a href="#Figure-3_002e29">Figure 3.29</a> to demonstrate how the mutex implementation can fail by
allowing two processes to acquire the mutex at the same time.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e47"></a>Exercise 3.47:</strong> A semaphore (of size <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>) is a
generalization of a mutex.  Like a mutex, a semaphore supports acquire and
release operations, but it is more general in that up to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> processes can
acquire it concurrently.  Additional processes that attempt to acquire the
semaphore must wait for release operations.  Give implementations of semaphores
</p>
<ol>
<li> in terms of mutexes

</li><li> in terms of atomic <code>test-and-set!</code> operations.

</li></ol>
</blockquote>

<a id="Deadlock"></a>
<h5 class="subsubheading">Deadlock</h5>

<p>Now that we have seen how to implement serializers, we can see that account
exchanging still has a problem, even with the <code>serialized-exchange</code>
procedure above.  Imagine that Peter attempts to exchange <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>1</mn>
</mrow>
</math> with <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>2</mn>
</mrow>
</math>
while Paul concurrently attempts to exchange <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>2</mn>
</mrow>
</math> with <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>1</mn>
</mrow>
</math>.  Suppose that
Peter’s process reaches the point where it has entered a serialized procedure
protecting <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>1</mn>
</mrow>
</math> and, just after that, Paul’s process enters a serialized
procedure protecting <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>2</mn>
</mrow>
</math>.  Now Peter cannot proceed (to enter a serialized
procedure protecting <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>2</mn>
</mrow>
</math>) until Paul exits the serialized procedure
protecting <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>2</mn>
</mrow>
</math>.  Similarly, Paul cannot proceed until Peter exits the
serialized procedure protecting <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mi>a</mi>
  <mn>1</mn>
</mrow>
</math>.  Each process is stalled forever,
waiting for the other.  This situation is called a <a id="index-deadlock"></a>
<em>deadlock</em>.
Deadlock is always a danger in systems that provide concurrent access to
multiple shared resources.
</p>
<p>One way to avoid the deadlock in this situation is to give each account a
unique identification number and rewrite <code>serialized-exchange</code> so that a
process will always attempt to enter a procedure protecting the lowest-numbered
account first.  Although this method works well for the exchange problem, there
are other situations that require more sophisticated deadlock-avoidance
techniques, or where deadlock cannot be avoided at all.  (See <a href="#Exercise-3_002e48">Exercise 3.48</a> 
and <a href="#Exercise-3_002e49">Exercise 3.49</a>.)<a class="footnote_link" id="DOCF176" href="#FOOT176"><sup>176</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e48"></a>Exercise 3.48:</strong> Explain in detail why the
deadlock-avoidance method described above, (i.e., the accounts are numbered,
and each process attempts to acquire the smaller-numbered account first) avoids
deadlock in the exchange problem.  Rewrite <code>serialized-exchange</code> to
incorporate this idea.  (You will also need to modify <code>make-account</code> so
that each account is created with a number, which can be accessed by sending an
appropriate message.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e49"></a>Exercise 3.49:</strong> Give a scenario where the
deadlock-avoidance mechanism described above does not work.  (Hint: In the
exchange problem, each process knows in advance which accounts it will need to
get access to.  Consider a situation where a process must get access to some
shared resources before it can know which additional shared resources it will
require.)
</p></blockquote>

<a id="Concurrency_002c-time_002c-and-communication"></a>
<h5 class="subsubheading">Concurrency, time, and communication</h5>

<p>We’ve seen how programming concurrent systems requires controlling the ordering
of events when different processes access shared state, and we’ve seen how to
achieve this control through judicious use of serializers.  But the problems of
concurrency lie deeper than this, because, from a fundamental point of view,
it’s not always clear what is meant by “shared state.”
</p>
<p>Mechanisms such as <code>test-and-set!</code> require processes to examine a global
shared flag at arbitrary times.  This is problematic and inefficient to
implement in modern high-speed processors, where due to optimization techniques
such as pipelining and cached memory, the contents of memory may not be in a
consistent state at every instant.  In contemporary multiprocessing systems,
therefore, the serializer paradigm is being supplanted by new approaches to
concurrency control.<a class="footnote_link" id="DOCF177" href="#FOOT177"><sup>177</sup></a>
</p>
<p>The problematic aspects of shared state also arise in large, distributed
systems.  For instance, imagine a distributed banking system where individual
branch banks maintain local values for bank balances and periodically compare
these with values maintained by other branches.  In such a system the value of
“the account balance” would be undetermined, except right after
synchronization.  If Peter deposits money in an account he holds jointly with
Paul, when should we say that the account balance has changed—when the
balance in the local branch changes, or not until after the synchronization?
And if Paul accesses the account from a different branch, what are the
reasonable constraints to place on the banking system such that the behavior is
“correct”?  The only thing that might matter for correctness is the behavior
observed by Peter and Paul individually and the “state” of the account
immediately after synchronization.  Questions about the “real” account
balance or the order of events between synchronizations may be irrelevant or
meaningless.<a class="footnote_link" id="DOCF178" href="#FOOT178"><sup>178</sup></a>
</p>
<p>The basic phenomenon here is that synchronizing different processes,
establishing shared state, or imposing an order on events requires
communication among the processes.  In essence, any notion of time in
concurrency control must be intimately tied to communication.<a class="footnote_link" id="DOCF179" href="#FOOT179"><sup>179</sup></a>  It is intriguing that a
similar connection between time and communication also arises in the Theory of
Relativity, where the speed of light (the fastest signal that can be used to
synchronize events) is a fundamental constant relating time and space.  The
complexities we encounter in dealing with time and state in our computational
models may in fact mirror a fundamental complexity of the physical universe.
</p>
<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT162"><p><a class="footnote_backlink" href="#DOCF162"><sup>162</sup></a>
Most real
processors actually execute a few operations at a time, following a strategy
called <a id="index-pipelining"></a>
<em>pipelining</em>.  Although this technique greatly improves the
effective utilization of the hardware, it is used only to speed up the
execution of a sequential instruction stream, while retaining the behavior of
the sequential program.</p>
</div>
<div id="FOOT163"><p><a class="footnote_backlink" href="#DOCF163"><sup>163</sup></a>
To quote some graffiti seen on a Cambridge building wall:
“Time is a device that was invented to keep everything from happening at
once.”</p>
</div>
<div id="FOOT164"><p><a class="footnote_backlink" href="#DOCF164"><sup>164</sup></a>
An even worse failure for this system could occur if
the two <code>set!</code> operations attempt to change the balance simultaneously, in
which case the actual data appearing in memory might end up being a random
combination of the information being written by the two processes.  Most
computers have interlocks on the primitive memory-write operations, which
protect against such simultaneous access.  Even this seemingly simple kind of
protection, however, raises implementation challenges in the design of
multiprocessing computers, where elaborate <a id="index-cache_002dcoherence"></a>
<em>cache-coherence</em> protocols
are required to ensure that the various processors will maintain a consistent
view of memory contents, despite the fact that data may be replicated
(“cached”) among the different processors to increase the speed of memory
access.</p>
</div>
<div id="FOOT165"><p><a class="footnote_backlink" href="#DOCF165"><sup>165</sup></a>
The
factorial program in <a href="3_002e1.xhtml#g_t3_002e1_002e3">3.1.3</a> illustrates this for a single
sequential process.</p>
</div>
<div id="FOOT166"><p><a class="footnote_backlink" href="#DOCF166"><sup>166</sup></a>
The
columns show the contents of Peter’s wallet, the joint account (in Bank1),
Paul’s wallet, and Paul’s private account (in Bank2), before and after each
withdrawal (W) and deposit (D).  Peter withdraws $10 from Bank1; Paul deposits
$5 in Bank2, then withdraws $25 from Bank1.</p>
</div>
<div id="FOOT167"><p><a class="footnote_backlink" href="#DOCF167"><sup>167</sup></a>
<a id="Footnote-167"></a>A more formal
way to express this idea is to say that concurrent programs are inherently
<a id="index-nondeterministic"></a>
<em>nondeterministic</em>. That is, they are described not by single-valued
functions, but by functions whose results are sets of possible values.  In
<a href="4_002e3.xhtml#g_t4_002e3">4.3</a> we will study a language for expressing nondeterministic
computations.</p>
</div>
<div id="FOOT168"><p><a class="footnote_backlink" href="#DOCF168"><sup>168</sup></a>
<code>Parallel-execute</code> is not part of standard Scheme,
but it can be implemented in <abbr>MIT</abbr> Scheme.  In our implementation, the
new concurrent processes also run concurrently with the original Scheme
process.  Also, in our implementation, the value returned by
<code>parallel-execute</code> is a special control object that can be used to halt
the newly created processes.</p>
</div>
<div id="FOOT169"><p><a class="footnote_backlink" href="#DOCF169"><sup>169</sup></a>
We have simplified <code>exchange</code> by exploiting the fact
that our <code>deposit</code> message accepts negative amounts.  (This is a serious
bug in our banking system!)</p>
</div>
<div id="FOOT170"><p><a class="footnote_backlink" href="#DOCF170"><sup>170</sup></a>
If the account
balances start out as $10, $20, and $30, then after any number of concurrent
exchanges, the balances should still be $10, $20, and $30 in some order.
Serializing the deposits to individual accounts is not sufficient to guarantee
this.  See <a href="#Exercise-3_002e43">Exercise 3.43</a>.</p>
</div>
<div id="FOOT171"><p><a class="footnote_backlink" href="#DOCF171"><sup>171</sup></a>
<a href="#Exercise-3_002e45">Exercise 3.45</a> investigates why deposits and withdrawals
are no longer automatically serialized by the account.</p>
</div>
<div id="FOOT172"><p><a class="footnote_backlink" href="#DOCF172"><sup>172</sup></a>
The
term “mutex” is an abbreviation for <a id="index-mutual-exclusion"></a>
<em>mutual exclusion</em>.  The general
problem of arranging a mechanism that permits concurrent processes to safely
share resources is called the mutual exclusion problem.  Our mutex is a simple
variant of the <a id="index-semaphore"></a>
<em>semaphore</em> mechanism (see <a href="#Exercise-3_002e47">Exercise 3.47</a>), which
was introduced in the “THE” Multiprogramming System developed at the
Technological University of Eindhoven and named for the university’s initials
in Dutch (<a href="References.xhtml#Dijkstra-1968a">Dijkstra 1968a</a>).  The acquire and release operations were originally
called P and V, from the Dutch words <em>passeren</em> (to pass) and
<em>vrijgeven</em> (to release), in reference to the semaphores used on railroad
systems.  Dijkstra’s classic exposition (<a href="References.xhtml#g_t1968b">1968b</a>) was one of the first to clearly
present the issues of concurrency control, and showed how to use semaphores to
handle a variety of concurrency problems.</p>
</div>
<div id="FOOT173"><p><a class="footnote_backlink" href="#DOCF173"><sup>173</sup></a>
In most time-shared operating systems, processes that
are blocked by a mutex do not waste time “busy-waiting” as above.  Instead,
the system schedules another process to run while the first is waiting, and the
blocked process is awakened when the mutex becomes available.</p>
</div>
<div id="FOOT174"><p><a class="footnote_backlink" href="#DOCF174"><sup>174</sup></a>
In <abbr>MIT</abbr> Scheme for a single processor, which uses a
time-slicing model, <code>test-and-set!</code> can be implemented as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">test-and-set! cell</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">without-interrupts
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> cell</span><span class="clo">)</span><span class="pln">
         true
         </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-car! cell true</span><span class="clo">)</span><span class="pln">
                false</span><span class="clo">)))))</span></pre></div>

<p><code>Without-interrupts</code> disables time-slicing interrupts while its procedure
argument is being executed.</p>
</div>
<div id="FOOT175"><p><a class="footnote_backlink" href="#DOCF175"><sup>175</sup></a>
There are many variants of such instructions—including
test-and-set, test-and-clear, swap, compare-and-exchange, load-reserve, and
store-conditional—whose design must be carefully matched to the machine’s
processor-memory interface.  One issue that arises here is to determine what
happens if two processes attempt to acquire the same resource at exactly the
same time by using such an instruction.  This requires some mechanism for
making a decision about which process gets control.  Such a mechanism is called
an <a id="index-arbiter"></a>
<em>arbiter</em>.  Arbiters usually boil down to some sort of hardware
device.  Unfortunately, it is possible to prove that one cannot physically
construct a fair arbiter that works 100% of the time unless one allows the
arbiter an arbitrarily long time to make its decision.  The fundamental
phenomenon here was originally observed by the fourteenth-century French
philosopher Jean Buridan in his commentary on Aristotle’s <i>De caelo</i>.
Buridan argued that a perfectly rational dog placed between two equally
attractive sources of food will starve to death, because it is incapable of
deciding which to go to first.</p>
</div>
<div id="FOOT176"><p><a class="footnote_backlink" href="#DOCF176"><sup>176</sup></a>
The general technique for avoiding
deadlock by numbering the shared resources and acquiring them in order is due
to <a href="References.xhtml#Havender-_00281968_0029">Havender (1968)</a>.  Situations where deadlock cannot be avoided require
<a id="index-deadlock_002drecovery"></a>
<em>deadlock-recovery</em> methods, which entail having processes “back out”
of the deadlocked state and try again.  Deadlock-recovery mechanisms are widely
used in database management systems, a topic that is treated in detail in 
<a href="References.xhtml#Gray-and-Reuter-1993">Gray and Reuter 1993</a>.</p>
</div>
<div id="FOOT177"><p><a class="footnote_backlink" href="#DOCF177"><sup>177</sup></a>
One such alternative to serialization is called
<a id="index-barrier-synchronization"></a>
<em>barrier synchronization</em>.  The programmer permits concurrent processes
to execute as they please, but establishes certain synchronization points
(“barriers”) through which no process can proceed until all the processes
have reached the barrier.  Modern processors provide machine instructions that
permit programmers to establish synchronization points at places where
consistency is required.  The <abbr>PowerPC</abbr>, for example, includes for
this purpose two instructions called <abbr>SYNC</abbr> and <abbr>EIEIO</abbr> 
(Enforced In-order Execution of Input/Output).</p>
</div>
<div id="FOOT178"><p><a class="footnote_backlink" href="#DOCF178"><sup>178</sup></a>
This may seem like a strange point of view, but there are
systems that work this way.  International charges to credit-card accounts, for
example, are normally cleared on a per-country basis, and the charges made in
different countries are periodically reconciled.  Thus the account balance may
be different in different countries.</p>
</div>
<div id="FOOT179"><p><a class="footnote_backlink" href="#DOCF179"><sup>179</sup></a>
For
distributed systems, this perspective was pursued by <a href="References.xhtml#Lamport-_00281978_0029">Lamport (1978)</a>, who showed
how to use communication to establish “global clocks” that can be used to
establish orderings on events in distributed systems.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="3_002e5.xhtml#g_t3_002e5" accesskey="n" rel="next">3.5</a>, Prev: <a href="3_002e3.xhtml#g_t3_002e3" accesskey="p" rel="prev">3.3</a>, Up: <a href="#g_t3_002e4" accesskey="u" rel="prev">3.4</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>